#二分查找
def binary_search(arr, key):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] < key:
            left = mid + 1
        elif arr[mid] > key:
            right = mid - 1
        else:
            return mid
    return -1
#顺序查找
def linear_search(arr, key):
    for index in range(len(arr)):
        if arr[index] == key:
            return index   
    return -1
#插值查找
   # mid = int((key - arr[left]) / (arr[right] - arr[left]) * (right - left)) + left
def interpalotion_search(arr, key):
    left = 0
    right = len(arr) - 1
    while True:
        mid = int((key - arr[left]) / (arr[right] - arr[left]) * (right - left)) + left
        if mid < left or mid > right:
            mid  = -1
            break
        if arr[mid] < key:
            left = mid + 1
        elif arr[mid] > key:
            right = mid - 1
        else:
            break
        if left > right:
            return -1
    return mid


arr = [1,2,3,4,5,6,7,8,9,100]

# print(linear_search(arr, 8))
# print(binary_search(arr, 1))
# print(interpalotion_search(arr, 100))
#排序
#选择排序
# 选择排序 O(n^2)
"""
从前往后 每一个元素都要跟其后面的其他元素作比较
如果出现左大右小 则进行交换
"""

def selection_sort(arr):
    for i in range(len(arr) - 1):
        for j in range(i + 1, len(arr)):
            if arr[i] > arr[j]:
                arr[i], arr[j] = arr[j], arr[i]

#优化
def selection_sort(arr):
    for i in range(len(arr) - 1):
        mid_value = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[mid_value]:
                min_value = j
        arr[i], arr[min_value] = arr[min_value], arr[i]
# 冒泡 O(n^2)
"""
从前往后 元素之间两两进行比较 
如果左大右小则交换
"""
def bubble_sort(arr):
    for i in range(len(arr) - 1):
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

arr = [5, 6, 8, 7, 2, 1, 5, 6, 9, 8, 5, 4, 1, 3, 2]
# selection_sort(arr)
bubble_sort(arr)
print(arr)